package org.example.SolutionNew001;

import java.util.ArrayList;
import java.util.List;

public class Matrix02 {
    public static void main(String[] args) {
        Matrix02 m = new Matrix02();
        int[][] matrix=new int[][]{{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(m.spiralOrder(matrix));
    }

    public List<Integer> spiralOrder1(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int topRow = 0, bottomRow = m-1, leftCol = 0, rightCol = n-1;
        List<Integer> res = new ArrayList<Integer>();
        while(topRow<m && bottomRow>=0 && leftCol<n && rightCol>=0&&topRow<=bottomRow && leftCol<=rightCol){
            for(int i=leftCol;i<=rightCol;i++){
                res.add(matrix[topRow][i]);
            }
            topRow++;
            for(int i=topRow;i<=bottomRow;i++){
                res.add(matrix[i][rightCol]);
            }
            rightCol--;
            if(topRow<=bottomRow && leftCol<=rightCol){
                for(int i=rightCol;i>=leftCol;i--){
                    res.add(matrix[bottomRow][i]);
                }
                bottomRow--;
            }else{
                break;
            }
            if(topRow<=bottomRow && leftCol<=rightCol){
                for(int i=bottomRow;i>=topRow;i--){
                    res.add(matrix[i][leftCol]);
                }
                leftCol++;
            }else{
                break;
            }
        }
        return res;
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        if(matrix==null||matrix.length==0||matrix[0].length==0) return res;
        boolean[][] visited = new boolean[m][n];
        int count = m*n;
        int[][] direction=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        int row = 0, col = 0,dir=0;
        for(int i=0; i<count; i++){
            res.add(matrix[row][col]);
            visited[row][col] = true;
            int nextRow=row+direction[dir][0], nextCol=col+direction[dir][1];
            if(nextRow<0 || nextRow>=m || nextCol<0 || nextCol>=n || visited[nextRow][nextCol]){
                dir=(dir+1)%4;
            }
            row+=direction[dir][0];
            col+=direction[dir][1];
        }
        return res;
    }
}
